package com.zhang.study.chapter03;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static com.zhang.util.RandomArrayUtil.generateRandomArray;

/**
 * 使用数组实现双端队列
 */
public class Code07_ArrayMyDeque {

    public static class ArrayMyDeque<T> {
        // 队列元素存储的数组
        private Object[] elements;
        // 队首位置，指向队列第一个元素的下一个位置
        private int head;
        // 队尾位置，指向队列最后一个元素的下一个位置
        private int tail;
        // 队列中的元素数量
        private int size;

        public ArrayMyDeque(int capacity) {
            elements = new Object[capacity]; // 创建一个指定容量的Object数组
            head = 0; // 初始化队首位置
            tail = 0; // 初始化队尾位置
            size = 0; // 初始化队列大小为0
        }

        // 在队尾添加元素
        public void addLast(T ele) {
            if (size == elements.length) {
                throw new RuntimeException("deque is Full!");
            }

            elements[tail] = ele;
            tail = (tail + 1) & (elements.length - 1);
            size++;

        }

        // 在队尾删除元素
        public T popLast() {
            if (size == 0) {
                throw new RuntimeException("deque is empty!");
            }
            int lastIndex = (tail - 1) & (elements.length - 1);
            Object item = elements[lastIndex]; // 获取队尾元素
            elements[lastIndex] = null; // 释放队尾元素的引用
            tail = lastIndex; // 更新队尾位置为最后一个元素的索引
            size--; // 队列大小减1
            return (T) item;
        }

        // 在队首添加元素
        public void addFirst(T ele) {
            if (ele == null) {
                throw new NullPointerException("Cannot add null element to deque");
            }
            if (size == elements.length) {
                // 这里可以添加扩容逻辑，如果不希望扩容，则抛出异常或返回false
                throw new IllegalStateException("Deque is full and cannot be expanded");
            }
            head = (head - 1) & (elements.length - 1); // 循环回到数组开头
            elements[head] = ele;
            size++;
        }

        // 在队首删除元素
        public T popFirst() {
            if (size == 0) {
                throw new NoSuchElementException("Deque is empty");
            }
            T result = (T) elements[head];
            elements[head] = null; // 清除旧元素引用
            head = (head + 1) & (elements.length - 1); // 移动到下一个位置
            size--;
            return result;
        }

    }

    public static void main(String[] args) {
        int len = 5;
        int value = 10;
        int testTime = 1;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            // 生成链表头结点
            int[] intArr = generateRandomArray(len, value);
            List<Integer> collect = IntStream.of(intArr).boxed().collect(Collectors.toList());
            ArrayMyDeque<Integer> arrayMyDeque = new ArrayMyDeque<>(16);
            LinkedList<Integer> linkedList = new LinkedList<>();
            ArrayDeque<Integer> integers = new ArrayDeque<>();
            for (Integer integer : collect) {
                arrayMyDeque.addFirst(integer);
                integers.addFirst(integer);
                linkedList.addFirst(integer);
            }
            if (!testQueue(arrayMyDeque, linkedList)) {
                System.out.println("Oops!");
                System.out.println("arrayMyDeque");
                while (arrayMyDeque.size != 0) {
                    System.out.print(arrayMyDeque.popLast() + "\t");
                }
                System.out.println(" ");
                System.out.println("linkedList");
                while (!linkedList.isEmpty()) {
                    System.out.print(linkedList.removeLast() + "\t");
                }
                System.out.println(" ");
                System.out.println("ArrayDeque");
                while (!integers.isEmpty()) {
                    System.out.print(integers.removeLast() + "\t");
                }
                System.out.println(" ");

            }
        }
        System.out.println("test finish!");

    }


    private static boolean testQueue(ArrayMyDeque<Integer> arrayMyDeque, LinkedList<Integer> linkedList) {
        int times = linkedList.size() - 1;
        while (times >= 0) {
            double random = Math.random();
            int i = (int) (Math.random() * 100 - Math.random() * 10);
            if (random >= 0.75) {
                // 从头部加一个元素
                arrayMyDeque.addFirst(i);
                linkedList.addFirst(i);
            } else if (random >= 0.5) {
                // 从尾部加一个元素
                arrayMyDeque.addLast(i);
                linkedList.addLast(i);
            } else if (random >= 0.25) {
                // 从头部删除一个元素
                Integer integer = arrayMyDeque.popFirst();
                Integer integer1 = linkedList.removeFirst();
                if (testValid(integer, integer1)) return false;
            } else {
                // 从尾部删除一个元素
                Integer integer = arrayMyDeque.popLast();
                Integer integer1 = linkedList.removeLast();
                if (testValid(integer, integer1)) return false;
            }
            times--;
        }
        while (!linkedList.isEmpty()) {
            Integer integer = arrayMyDeque.popFirst();
            Integer first = linkedList.removeFirst();
            if (!Objects.equals(integer, first)) {
                return false;
            }
        }
        return true;
    }

    private static boolean testValid(Integer integer, Integer integer1) {
        if ((integer == null && integer1 != null) || (integer1 == null && integer != null)) {
            return true;
        }
        if (!(integer == null)) {
            return !integer.equals(integer1);
        }
        return false;
    }
}
